#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define N 5500000
#define eps 1e-7
#define ll long long
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
const int inf=2147483647;
int a[N];
struct Splay
{
    int size,w[N],fa[N],sz[N],cnt[N],root[N],son[N][2];
    inline void pushup(int x)
    {
        sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
    }
    inline bool getson(int x)
    {
        return son[fa[x]][1]==x;
    }
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y],tx=getson(x),ty=getson(y),p=son[x][!tx];
        fa[x]=z;son[z][ty]=x;
        fa[y]=x;son[x][!tx]=y;
        fa[p]=y;son[y][tx]=p;
        pushup(y);pushup(x);
    }
    void splay(int x,int k,int goal)
    {
        while(fa[x]!=goal)
        {
            int y=fa[x],z=fa[y];
            if(z!=goal)rotate((getson(x)==getson(y))?y:x);
            rotate(x);
        }
        if(!goal)root[k]=x;
    }
    void find(int x,int k)
    {
        int id=root[k];
        while(son[id][x>w[id]]&&x!=w[id])id=son[id][x>w[id]];
        splay(id,k,0);
    }
    int nxt(int x,int k,int p)
    {
        find(x,k);
        int id=root[k];
        if((!p&&w[id]<x)||(p&&w[id]>x))return id;
        id=son[id][p];
        while(son[id][!p])id=son[id][!p];
        return id;
    }
    int get(int x,int k)
    {
        int id=nxt(x,k,0);
        splay(id,k,0);
        return sz[son[id][0]]+cnt[id]-1;
    }
    void insert(int x,int k)
    {
        int id=root[k],ff=0;
        while(id&&w[id]!=x)
        {
            ff=id;
            id=son[id][x>w[id]];
        }
        if(id)cnt[id]++;
        else
        {
            id=++size;
            sz[id]=cnt[id]=1;
            w[id]=x;fa[id]=ff;
            if(ff)son[ff][x>w[ff]]=id;
        }
        splay(id,k,0);
    }
    void delate(int x,int k)
    {
        int pre=nxt(x,k,0); 
        int suf=nxt(x,k,1);
        splay(pre,k,0);
        splay(suf,k,pre);
        int id=son[suf][0];
        cnt[id]--;
        if(!cnt[id])fa[id]=0,son[suf][0]=0;
        else splay(id,k,0);
    }
}S;
struct Segment_Tree
{
    #define lson lc[o]
    #define rson rc[o]
    #define mid ((l+r)>>1)
    int size,lc[N],rc[N];
    inline void insert(int &o)
    {
        if(!o)o=++size;
    }
    void build(int &o,int l,int r)
    {
        insert(o);
        S.insert(-inf,o);S.insert(+inf,o);
        for(int i=l;i<=r;i++)S.insert(a[i],o);
        if(l==r)return;
        build(lson,l,mid);build(rson,mid+1,r);
    }
    void optset(int o,int l,int r,int q,int num)
    {
    	if(a[q]==num)return;
        S.delate(a[q],o);S.insert(num,o);
        if(l==r){a[q]=num;return;}
        if(q<=mid)optset(lson,l,mid,q,num);
        else optset(rson,mid+1,r,q,num);
    }
    int query(int o,int l,int r,int ql,int qr,int num)
    {
        if(ql<=l&&r<=qr)
        {
            int ans=S.get(num,o);
            return ans;
        }
        int ans=0;
        if(ql<=mid)ans+=query(lson,l,mid,ql,qr,num);
        if(qr>mid)ans+=query(rson,mid+1,r,ql,qr,num);
        return ans;
    }
    int getnxt(int o,int l,int r,int ql,int qr,int num,int p)
    {
        if(ql<=l&&r<=qr)return S.w[S.nxt(num,o,p)];
        int ans=p?+inf:-inf;
        if(ql<=mid)
        {
            int x=getnxt(lson,l,mid,ql,qr,num,p);
            ans=p?min(ans,x):max(ans,x); 
        }
        if(qr>mid)
        {
            int x=getnxt(rson,mid+1,r,ql,qr,num,p);
            ans=p?min(ans,x):max(ans,x);
        }
        return ans;
    }
    #undef mid
}T;
int main()
{
    int n=read(),m=read(),root=0,i,flag,l,r,x;
    for(i=1;i<=n;i++)a[i]=read();
    T.build(root,1,n);
    for(i=1;i<=m;i++)
    {
        flag=read();
        if(flag!=3)l=read(),r=read(),x=read();
        else x=read();
        if(flag==1)printf("%d\n",T.query(root,1,n,l,r,x)+1);
        if(flag==2)
        {
            int lt=0,rt=1e8+7,mt;
            while(lt<rt)
            {
                mt=((lt+rt)>>1)+1;
                if(T.query(root,1,n,l,r,mt)+1>x)rt=mt-1;
                else lt=mt;
            }
            printf("%d\n",lt);
        }
        if(flag==3)T.optset(root,1,n,x,read());
        if(flag==4)printf("%d\n",T.getnxt(root,1,n,l,r,x,0));
        if(flag==5)printf("%d\n",T.getnxt(root,1,n,l,r,x,1));
    }
    return 0;
}
